package com.gxc.integer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 60. 排列序列
 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

 "123"
 "132"
 "213"
 "231"
 "312"
 "321"
 给定 n 和 k，返回第 k 个排列。
 */
public class GetPermutation {

    public static void main(String[] args) {
        System.out.println(handle(3, 3));
        System.out.println(handle(4, 9));
        System.out.println(handle(3, 1));
        System.out.println(handle(3, 6));

        System.out.println(handle(3, 2));
    }

    public static String handle(int n, int k) {
        List<String> list = new ArrayList<>();
        int res = 1;
        for (int i = 1; i <= n; i++) {
            list.add(i + "");
        }
        for (int i = 1; i <= n; i++) {
            res = res * i;
        }

        StringBuffer sb = new StringBuffer();
        int index = n;
        while (k>1) {
            res = res/index;
            if (k % res == 0) {
                int i = (k - 1) / res;
                sb.append(list.remove((k-1)/res));
                k = k - res * i;
            } else {
                sb.append(list.remove(k/res));
                k = k % res;
            }
            index--;
        }
        for (String s : list) {
            sb.append(s);
        }

        return sb.toString();
    }

    /**
     * k'=(k−1)mod(n−1)!+1
     */
    class Solution {
        public String getPermutation(int n, int k) {
            int[] factorial = new int[n];
            factorial[0] = 1;
            //n的对数
            for (int i = 1; i < n; ++i) {
                factorial[i] = factorial[i - 1] * i;
            }
            // k = k-1 的原因，是元素从 1 开始的第K位， 转成从0开始的第k-1 位
            --k;
            StringBuffer ans = new StringBuffer();
            //数字 1。。。。。。n
            int[] valid = new int[n + 1];
            Arrays.fill(valid, 1);
            for (int i = 1; i <= n; ++i) {
                //计算 多少个   (n-1)!
                int order = k / factorial[n - i] + 1;
                //排除已经用过的元素
                for (int j = 1; j <= n; ++j) {
                    order -= valid[j];
                    if (order == 0) {
                        ans.append(j);
                        valid[j] = 0;
                        break;
                    }
                }
                k %= factorial[n - i];
            }
            return ans.toString();
        }
    }


}
